Datacenters providing cloud computing services typically include routers, switches, bridges, and other physical network devices that interconnect a large number of servers, network storage devices, and other types of physical computing devices via wired or wireless network links. The individual servers can host one or more virtual machines or other types of virtualized components accessible to cloud computing clients. The virtual machines can exchange messages such as emails via virtual networks in accordance with one or more network protocols supported by the physical network devices.